package searchStudy;

public class GetNumberOfK {

    /**
     * JZ37 数字在升序数组中出现的次数
     * @param args
     */
    public static void main(String[] args) {

    }

    public int GetNumberOfK(int [] array , int k) {
        //二分查找获得下标
        //找到第一个大于等于k的值
        int leftIndex = binarySearch(array, k, true);
        int rightIndex = binarySearch(array, k, false);
        if (leftIndex == array.length || array[leftIndex] != k){
            return 0;
        }
        return rightIndex - leftIndex;
    }

    //二分查找
    public int binarySearch(int[] array, int k, boolean flag){
        int high = array.length - 1;
        int low = 0;
        int ans = array.length;
        while (low <= high){
            int mid = (low + high) >> 1;
            if (array[mid] > k || (flag && array[mid] >= k)){
                high = mid - 1;
                ans = mid;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
}
